import java.util.HashSet;
import java.util.Set;

public class LongestConsecutive {
    // leetcode hot 100 最长连续序列
    //https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
    public int longestConsecutive(int[] nums) {
        // 遍历两遍数组，第一遍将数组中存在的元素记录在set中
        // 第二遍遍历数组进行最长序列的记录，要想得到最长的连续序列，那么最长序列的第一个数的前面肯定不能
        // 有元素，所以我们遍历的时候，就从set中检查该元素的前一个元素是否存在，如果存在我们就不枚举，
        // 不存在我们才枚举出可能的情况
        if (nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            if (!set.contains(n)) set.add(n);
        }
        int maxLength = 1;
        for (Integer n : set) {
            // 不存在n-1的元素，那么该元素可能是最长序列的第一个元素，所以我们从该元素开始枚举
            if (!set.contains(n-1)) {
                int length = 1;
                while (set.contains(++n)) {
                    length++;
                    maxLength = Math.max(maxLength,length);
                }
            }
        }
        return maxLength;
    }
}
